package leetcode_滑动窗口;

/**
 * 76.最小覆盖子串
 * 算法：滑动窗口
 *
 * @author yezh
 * @date 2023/12/29 15:57
 */
public class _76 {

    public String minWindow(String s, String t) {
        int ansL = 0, ansR = 0, need = t.length(), minLen = Integer.MAX_VALUE;
        // 字符串 t 拥有的字符数
        int[] cnt = new int[128];
        for (int i = 0; i < t.length(); i++) ++cnt[t.charAt(i)];
        for (int l = 0, r = 0; r < s.length(); ++r) {
            if (--cnt[s.charAt(r)] >= 0) --need;
            // need = 0, 表示 t 中的所有字符都在滑动窗口中出现
            while (need == 0) {
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    ansL = l;
                    ansR = r + 1;
                }
                // cnt[s.charAt(l)] = 0: 表示 s.charAt(l) 在 t 中
                if (++cnt[s.charAt(l)] > 0) ++need;
                ++l;
            }
        }
        return s.substring(ansL, ansR);
    }

}
